1.1 Field of the Invention
The present invention relates to an automatic method of computerized optimization of a technical system like for instance routing systems such as a transportation routing system or a communication network or a supply chain system.
1.2 Description and Disadvantages of Prior Art
State of the art comprises a rich set of classical improvement heuristics of optimization approaches of technical systems. For comparison reasons the different approaches are often applied to published problem instances which are already extensively studied in the literature as the famous Traveling Salesman Problem which was often considered in the literature. For instance G. Reinelt, TSPLIB95, University of Heidelberg, Germany, 1995 and M. Grotschel, O. Holland, Math. Prog. 1991, 51, 141 published such an extensively studied set of traveling salesman problems. Also the problem set of M. Solomon, Operations Research, 1987, 35, 254 could be mentioned at this place.
Optimization of many technical systems can be stated as optimization of a routing system. Due to their importance routing systems have been subject of extensive studies. With respect to the technical problem of transportation routing the following state of the art work could be mentioned:
S. R. Thangiah, I. H. Osman, T. Sun, Hybrid Genetic Algorithm, Simulated Annealing and Tabu Search Methods for Vehicle Routing Problems with Time Windows, working paper, 1994), UKC/OR94/4; J.-Y. Potvin, S. Begio, 1994, A Genetic Approach to the Vehicle Routing Problem with Time Windows, Publication CRT-953, Centre de recherche sur les transports, Universite de Montreal; P. M. Thompson, H. Psaraftis, 1989, Cyclic Transfer Algorithms for Multi-Vehicle Routing and Scheduling Problems, Operations Research 41, 935-946; J.-Y. Potvin, T. Kervahut, B.-L. Garcia, J.-M. Rousseau, 1993, A Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows, Publication CRT-855, Centre de recherche sur les transports, Universite de Montreal; W.-C. Chiang, R. Russell, 1993, Simulated Annealing Metaheuristics for the Vehicle Routing Problem with Time Windows, working paper, Department of Quantitative Methods, University of Tulsa, Tulsa, OK 74104; Y. Rochat, E. Taillard, Probabilistic diversification and intensification in local search for vehicle routing, Journal of Heuristics, Vol 1, No 1, 1995, 147-67.
With respect to the applied methods the following important approaches can be distinguished within the state of the art:
1.2.1 Simulated Annealing and its Relatives
Simulated Annealing as outlined for example in N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, E. Teller, J. Chem. Phys. 1953, 21, 1087., S. Kirkpatrick, C. D. Gelatt Jr., M. P. Vecchi, Science, 1983, 220, 671, S. Kirkpatrick, G. Toulouse, J. Physique, 1985, 46, 1277., Threshold Accepting as outlined for example in G. Dueck, T. Scheuer, J. Comp. Phys., 1990, 90, 161, the Great Deluge Algorithm as outlined for example in G. Dueck, J. Comp. Phys., 1993, 104, 86, G. Dueck, T. Scheuer, H.-M. Wallmeier, Spektrum der Wissenschaft, March 1993, Record-to-Record Travel technique as outlined for example in G. Dueck, J. Comp. Phys., 1993, 104, 86, and related Monte Carlo-type optimization algorithms as outlined for example in K. Binder, D. W. Heermann, Monte Carlo Simulation in Statistical Physics, Springer, N.Y., 1992, T. J. P. Penna, Phys. Rev. E, 1995, 51, R1-R3 apply ideas of statistical physics and applied mathematics to find near-to-optimum solutions for combinatorial optimization problems. These are all iterative exchange algorithms. They start with an initial configuration and proceed by small exchanges in the actual or current solution to get a tentative new solution. The tentative new solution is evaluated, i.e. its objective function, e.g. its total cost, is computed. The algorithmic decision rule is applied. It is decided if the tentative new solution is kept as the current solution, in case of acceptance the new solution is taken as the new current solution.
1.2.1.1 Decision Rules
The different algorithms work with this same structure, but they use different decision rules for acceptance/rejection. The Random Walk (RW) accepts every new solution. The Greedy Algorithm (GRE) accepts every solution which is not worse than the current solution. Simulated Annealing procedures accept every better solution and, with a certain probability, also solutions being worse than the current solution. Threshold Accepting (TA) algorithms accept every solution which is not much worse than the current solution, where xe2x80x9cnot muchxe2x80x9d is defined by a threshold. The Great Deluge Algorithm rejects every solution below a required quality level (the xe2x80x9cwaterlinexe2x80x9d). This is in principle a Darwian approach. Instead of xe2x80x9cOnly the Fittest Will Survivexe2x80x9d the deluge principal works with xe2x80x9cOnly the Worst Will Die
1.2.1.2 Mutations
Of course, the definition of an exchange in a current solution depends on the optimization problem. Let us look, for instance, at the Traveling Salesman Problem. In order to modify the current solution to get a new tentative chosen solution, different types of Local Search mutations are commonly applied. An Exchange exchanges two nodes in the tour. The Lin-2-Opt approach cuts two connections in the tour and reconstructs a new tour by insertion of two new connections. A Node Insertion Move (NIM, or Lin-2.5-opt outlined for instance in E. Aarts, J. K. Lenstra, Local Search in Combinatorial Optimization, John Wiley and Sons, Chichester, 1997) removes a node from the tour and reinserts it at the best position. Moreover, Lin-3-Opt, Lin-4-Opt and Lin-5-Opt etc., outlined for instance in S. Lin, Bell System Techn. J., 1965}, 44, 2245, S. Lin, B. W. Kernighan, Oper. Res., 1973, 21, 498, are sometimes applied, cutting three, four, and five connections and choosing one of 4, 25, and 208 etc. possibilities to recreate the new tour, respectively.
1.2.2 Set Based Algorithms
Simulated Annealing and related techniques have in common that a new configuration is generated based on the actual one. No information about former configurations is used. Genetic Algorithms and Evolution Strategies both use a large set, of configurations as individua of a .population. Tabu Search saves information about former configurations in its Tabu List and therefore also depends on a set of configurations.
1.2.2.1 Genetic Algorithms and Evolution Strategies
Genetic Algorithms mostly use different kinds of crossover operators generating children from parent configurations, while Evolution Strategies concentrate on mutations altering a member of the population. With both techniques new configurations are produced; various implementations of these algorithms-only differ in the type of the used mutations and in the choice which configurations are allowed to reproduce or to mix with each other or forced to commit suicide.
1.2.2.2 Tabu Search
Tabu Search, outlined for instance in G. Reinelt, The Traveling Salesman, Springer, Heidelberg, 1994, is a memory based search strategy to guide the system being optimized away from parts of the solution space which were already explored. This can be achieved either by forbidding solutions already visited or structures some former solutions had in common, which are stored in a Tabu List. This list is updated after each mutation according to some proposed rules, which have to guarantee that the optimization run never reaches a solution again which was already visited before, that the Tabu List Size does not diverge, and that a good solution can be achieved.
1.2.3 Problems within Prior Art
For the basic well-known problems in combinatorial optimization these algorithms turned out to be successful for the construction of near-to-optimum solutions. Dealing with complex problems, however, we encountered in severe difficulties using these classical algorithms. If we considered steel mill schedules, airline schedules, wide area networks, or very complex tour planning tasks, we faced troubles.
Complex problems often can be seen as xe2x80x9cdiscontinuousxe2x80x9d: If we walk one step from a solution to a neighbour solution, the heights or qualities of these solutions can be dramatically different, i.e. the landscapes in these problem areas can be very xe2x80x9cunevenxe2x80x9d.
Solutions of complex problems often have to meet many constraints, and it is often even hard to get just admissible solutions. Neighbour solutions of complex schedules, for instance, are usually inadmissible solutions, and it may be very hard to walk in such a complex landscape from one admissible solution to another neighboured admissible solution. Many forms of the classical algorithms try to avoid the xe2x80x9cadmissibility problemxe2x80x9d by modeling artificial penalty functions, but they typically can get stuck in xe2x80x9cslightly inadmissiblexe2x80x9d solutions which might be not allowed at all.
1.3 Objective of the Invention
The invention is based on the objective to provide an improved method for optimization of technical systems. It is a further objective of the current invention to prevent that the automatic optimization process gets stucked in xe2x80x9cslightly inadmissiblexe2x80x9d solutions violating additional constraints xe2x80x9csligthlyxe2x80x9d.
The objective of the invention is solved by claim 1. The method for automatic, computer-based optimization of a technical system according to the current invention starts with a description of said technical system by a state {right arrow over (x)} with state-variables xv, v=1, . . . , N, The said technical system is rated in a state {right arrow over (x)} by a measure (a xe2x80x9ccost-functionxe2x80x9d, xe2x80x9cenergyxe2x80x9d, . . . ) f({right arrow over (x)}). The technical system may be for instance a routing system like a transportation routing system, a communication network or a supply chain system (for instance in the automobile industry) and the like. Said method determines an improved state {right arrow over (x)}opt with an improved measure f({right arrow over (x)}opt) and said improved state satisfying one or more additional constraints. Said method comprises an initialization-step as step 1, choosing a first state as current-state {right arrow over (y)} of said technical system said first state already satisfying said additional constraints. Said method comprises a ruin-step as step 2, destroying said current-state by selecting a subset B of said current-state""s state-variables yvxcexc, xcexc=1, . . . , M, and excluding them from the current-state building a reduced-state from the remaining state-variables. Said method comprises a recreation-step as step 3, determining a recreated-state {right arrow over (Z)}. Said recreated-state being determined by extending said reduced-state by substitute-state-variables Zyxcexc, substituting said excluded-state-variables of said subset B, and said recreated-state satisfying said additional constraints, and determination of said substitute-state-variables is not guided by the values of said excluded-state-variables. Said method comprises an acceptance-step as step 4, deciding if said recreated-state is to be accepted as a new current-state {right arrow over (y)}. Said method comprises an iteration-step as step 5, deciding if and how to iterate said method beginning with step 2.
As the technique proposed by the current invention explores from the very beginning (the first state) of the optimization process only states which satisfy the additional constraints (admissible states) by constructing them in accordance with the constraints thus that artificial constructions like penalty terms in the measure (also called xe2x80x9cobjective functionxe2x80x9d, xe2x80x9cenergyxe2x80x9d or the like) are not required for these constraints. One cannot emphasize enough that this property of the proposed method has tremendous implications. At every time during running an optimization one has a fully admissible solution available. This is in contrary to many other approaches where one is often left with small violations of the given restrictions which one has to resolve in practice by neglection, tolerance, by wiping them out by hand, by brute force or other postprocessing techniques. Always ending with an admissible solution significantly improves practicability. In practice, clean admissible solutions are more important than xe2x80x9cacceptablexe2x80x9d solutions with certain violations of the additional constraints. Moreover the current invention suggests destroying a subset of the current-state""s state variables and thus the method is destroying that state not in a small or local way only (for instance changing a certain value to a small extend only). Instead it teaches to destroy a larder part of the current-state. To ruin a quite large fraction of the state gives one the other additional freedom in the recreation-step. The important advantage is: If one has destroyed a large part of the previous state one has an increased freedom to create a new one. One can reasonably hope that, in this large space of possibilities, it is possible to achieve both: determining an admissible and an improved solution. Stated in more abstract terms the fundamental advantage of the current approach is to divide a large problem (in the worst and most complex case a NP-hard problem) into sequences of partial problems, which in the sum are easier to solve than the large problem. Especially the fact that the partial problems (the destroyed parts of the state) are smaller than the large problem but still are large enough to allow the method to explore larger areas of state space, makes the teaching very efficient in finding improved solutions in the global sense.
Based on these properties the current approach is thus better suited for xe2x80x9cdiscontinuousxe2x80x9d problems, xe2x80x9cproblems with very complex measures/objective functionsxe2x80x9d or xe2x80x9cproblems where the solutions have to meet many side conditionsxe2x80x9d. The efficiency improvements of the suggested method allow to find in shorter computing time states which are closer to the optimum state. Moreover as the ruin-step destroys larger parts of the current-state an improved state is much more independent from the state chosen as first state in the initialization-step. This also avoids that the method becomes xe2x80x9ctrappedxe2x80x9d in certain parts of state space.
According to a further embodiment of the current invention said recreation-step determines said substitute-state-variables by construction heuristics and/or exact algorithms recreation. Said recreation-step comprises a substep 3A of selecting at least one of said excluded-state-variables. Further said recreation-step comprises a substep 3B of calculating and assigning a value to said selected-state-variable. Moreover said recreation-step repeats said substeps 3A and 3B until all substitute-state-variables have been determined. In a further variant said recreation-step comprises a best-insertion-step which comprises a substep 3B of calculating and assigning to said selected-state-variable a value optimizing said measure f( ) of said reduced-state extended by said substitute-state-variable with respect to said selected-state-variable.
The proposed procedure of determining a recreated state offers an improved compromise of the complexity to be handled for calculating a recreated state, the quality of the new solutions and the processing speed for performing the required calculations. By selecting only a few of the excluded state variables for recalculation the whole task of xe2x80x9crecreatexe2x80x9d is further broken down in a sequence of partial and simpler tasks. On the other hand with respect to such a partial task the optimum substitute state variables are calculated. This makes sure that in any case a very good recreated state will be determined.
According to a further embodiment of the current invention said state-variables comprise specifications of a multitude of NNodes nodes, wherein a neighbourhood-relationship is defining distances between pairs of nodes. Within such a system said ruin-step comprises a radial-ruin-step, wherein a first node and its related state-variables are selected and excluded from said current-state {right arrow over (y)}. Then a random number Axe2x89xa7NNodes is determined and the Axe2x88x921 nearest nodes of said first node according to said neighbourhood-relationship are selected and the related state-variables of said Axe2x88x921 nearest nodes are excluded from said current-state y. As a further possibility said ruin-step comprises a random-ruin-step wherein a random number Axe2x89xa6NNodes is determined and A nodes are selected randomly and their state-variables are excluded from said current-state {right arrow over (y)}.
If the ruin operation takes place within a certain neigbourhood of a node it turns out that the optimization procedure is improved significantly. This can be understood as a neighourhoud relationship indicates some sort of xe2x80x9cexchangeabilityxe2x80x9d of said nodes. The neighbourhood relationship on the other hand is not limited to a mere geographical relationship of the node. It also may be based on properties assigned to and/or represented by said nodes.
According to a further embodiment of the current invention wherein said state-variables comprising specifications of a multitude of NNodes , and wherein said state-variables comprising specifications of sequences of said nodes. Within this embodiment the ruin-step comprises a sequential-ruin-step, wherein a first node and its related state-variables are selected and excluded from said current-state {right arrow over (y)}, and wherein a random number Axe2x89xa6NNodes is determined and the Axe2x88x921 preceding or succeeding nodes of said first node are selected and their related state-variables are excluded from said current-state {right arrow over (y)}. As a further possibility said ruin-step comprises a random-ruin-step, wherein a random number Axe2x89xa6Nodes is determined and A nodes are selected randomly and their state-variables are excluded from said current-state {right arrow over (y)}.
If within the technical system sequences of said nodes are defined a ruin operation relating to a certain segment of such a sequence turns out to improve the optimization procedure significantly.
According to a further embodiment of the current invention the technical system and said related state-variables describe a routing-system with a multitude of transfer-facilities serving a multitude of locations and said locations requesting transfer-demands between pairs of said locations. The measure are the transfer-costs. The invention teaches a ruin-step which comprises a demand-ruin-step wherein at least one transfer-demand is selected and wherein all state-variables relating to said selected-transfer-demand are selected and are excluded from said current-state {right arrow over (y)}. Within said recreation-step in substep 3A and 3B the state-variables relating to said selected-transfer-demand are calculated.
To ruin and recreate those state-variables which relate to a demand to be satisfied by said routing systems has the advantage that the reduced state results in a valid system state (of course with the exception that it is not satisfying the destroyed routing demand) and no complex additional determination for the reduced system state is necessary to satisfy the additional constraints. Moreover ruin and recreate operations relating to demands are to a large extend suited for parallel execution. For example in vehicle routing systems the recreate operations have to query all transportation facilities for recalculation of state variables; as xe2x80x9cindependent objectsxe2x80x9d said transportation facilities can be queried in parallel. Especially for very complex technical systems like in the current case (being NP-hard for instance) a method being suitable for parallel enablement is most important for performance gains.
According to a further embodiment of the current invention said routing-system is a transportation-routing-system wherein said transfer-facilities are transportation-facilities and wherein said transfer-demands are transportation-demands of transportation-sizes. According to the current invention said ruin-step comprises a transportation-demand-ruin-step, wherein a range of transportation-sizes is determined and wherein state-variables relating to transportation-demands within said range of transportation-sizes are selected and are excluded from said current-state {right arrow over (y)}. Moreover the inventions treats also transportation-routing-systems, wherein according to a time-window-constraint a transportation-demand is to be served within a time-window-interval. For such systems a ruin-step comprising a time-window-ruin-step is suggested, wherein a range of time-window-intervals is determined and wherein all state-variables relating to demands of time-window-intervals within said range of time-window-intervals are selected and are excluded from said current-state {right arrow over (y)}.
To ruin and recreate transfer-demands of xe2x80x9csimilarxe2x80x9d transfer-sizes or xe2x80x9csimilarxe2x80x9d time-window-intervals improves the recreate process. As demands being xe2x80x9csimilarxe2x80x9d in this sense may be exchanged in the routing solution with a greater probability without violating the constraints the recreate process will be accelerated.
According to a further embodiment of the current invention said routing-system describes a communication-network, wherein said locations are communication-nodes and wherein said multitude of transfer-demands are communication-demands between pairs of communication-nodes of certain bandwidths to be satisfied by a sequence of trunks, said trunks representing the transfer-facilities, connecting each of said pairs of communication-nodes. Said measure are the communication-costs. The invention teaches a ruin-step comprising a communication-demand-ruin-step, wherein at least one communication-demand is determined and state-variables related to the sequence of trunks connecting the pair of communication-nodes of said determined communication-demand are selected and are excluded from said current-state {right arrow over (y)}.
The advantages of this teaching are similar to the advantages outlined with the ruin and recreate operations based on demands in general given above.
According to a further embodiment of the current invention said initialization-step is determining said first state by executing said best-insertion-step using a reduced-state, for which all state-variables have been excluded.
Compared to an arbitrary. initial state above first state starts the optimization process already with a xe2x80x9cgoodxe2x80x9d solution much nearer to the optimum leading to a performance gain.
According to a further embodiment of the current invention the acceptance-step deciding, if said recreated-state is to be accepted as new current-state, is accepting said recreated-state: according to the random-walk-technique; and/or according to the greedy-acceptance-technique; and/or according to the simulating-annealing-technique; and/or according to the threshold-accepting-technique; and/or according to the great-deluge-technique; and/or according to the record-to-record-travel-technique.
Therefore the current RuinandRecreate approach can be combined with most known acceptance techniques indicating its flexibility and broad applicability.